﻿using System;
using System.Collections.Generic;
using System.Diagnostics.CodeAnalysis;
using System.Linq;
using System.Numerics;
using System.Reflection;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using Xunit;
namespace LeetCode.CodeDay
{
    public partial class Code
    {
        /// <summary>
        /// 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
        // 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
        // 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，
        // 其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
        /// </summary>
        /// <param name="args"></param>
        public void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            for (int i = 0; i < n; i++)
            {
                bool isInsert = false;
                for (int j = 0; j < m; j++)
                {
                    if (nums2[i] <= nums1[j])
                    {
                        nums1 = moveToNext(nums1, j);
                        nums1[j] = nums2[i];
                        isInsert = true;
                        break;
                    }
                }
                if (isInsert == false)
                    nums1[m + i] = nums2[i];
            }

            int[] moveToNext(int[] numOrigin, int sort)
            {
                int length = numOrigin.Length;
                for (int i = length - 1; i > sort; i--)
                {
                    numOrigin[i] = numOrigin[i - 1];
                    numOrigin[i - 1] = 0;
                }
                return numOrigin;
            }
        }

        /// <summary>
        /// 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        /// 你可以假设数组是非空的，并且给定的数组总是存在多数元素
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int MajorityElement(int[] nums)
        {
            var n = nums.Length;
            var result = new int[n, 2];
            int j = 0;
            for (int i = 0; i < n; i++)
            {
                bool exists = false;
                for (int k = j; k > -1; k--)
                {
                    if (result[k, 0] == nums[i])
                    {
                        result[k, 1]++;
                        exists = true;
                    }
                }
                if (exists == false)
                {
                    result[j, 0] = nums[i];
                    result[j, 1]++;
                    j++;
                }
            }
            for (int i = 0; i < n; i++)
            {
                if (result[i, 1] > n / 2)
                    return result[i, 0];
            }
            return 0;
        }
        /// <summary>
        /// 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="k"></param>
        public void Rotate(int[] nums, int k)
        {
            int n = nums.Length;
            if (n == 0 || n == 1) return;
            k = k % n;

            int[] rs = new int[n];

            for (int i = 0; i < n; i++)
            {
                rs[(i + k) % n] = nums[i];
            }

            int j1 = 0;
            while (j1 < n)
            {
                nums[j1] = rs[j1];
                j1++;
            }
        }
        /// <summary>
        /// 买卖股票的最佳时机
        /// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
        /// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
        /// 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit(int[] prices)
        {
            //[1,2]
            int amount = 0;
            int minIndex = 0;
            for (int i = 0; i < prices.Length; i++)
            {
                if (prices[minIndex] > prices[i])
                    minIndex = i;
                else
                {
                    if (prices[i] - prices[minIndex] > amount)
                        amount = prices[i] - prices[minIndex];
                }
            }
            return amount;
        }
        /// <summary>
        /// 买卖股票的最佳时机 II
        /// 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
        /// 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
        /// 返回 你能获得的 最大 利润 。
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int MaxProfit2(int[] prices)
        {
            int preVal = prices[0];
            int amount = 0;
            for (int i = 0; i < prices.Length; i++)
            {
                if (prices[i] > preVal)
                {
                    amount += prices[i] - preVal;
                }
                preVal = prices[i];
            }
            return amount;
        }
        /// <summary>
        ///  跳跃游戏
        /// 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
        /// 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public bool CanJump(int[] nums)
        {
            //[2,3,1,1,4]
            if (nums.Length == 1)
                return true;
            int max = 0;
            for (int i = 0; i <= max; i++)
            {
                if (max < nums[i] + i)
                    max = nums[i] + i;
                if (max >= (nums.Length - 1))
                    return true;
            }
            return false;
        }
        /// <summary>
        ///  跳跃游戏2
        /// 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
        /// 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
        /// 0 <= j <= nums[i]
        /// i + j<n
        /// 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
        /// </summary>
        /// <param name="prices"></param>
        /// <returns></returns>
        public int Jump2(int[] nums)
        {
            //int max = 0;
            //int nextMax = 0;
            //int curIndex = 0;
            //int nextMaxIndex = 0;
            //for (int i = 0; i <= max; i++)
            //{
            //    if (max < nums[i] + i && i >= max)
            //    {
            //        max = nums[i] + i;
            //        {
            //            if (nextMax < nums[i] + i)
            //            {
            //                nextMax = nums[i] + i;
            //            }
            //        }
            //    }

            //    if (max >= (nums.Length - 1))
            //        break;
            //}
            return 0;
        }
    }
}